<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>哈希表封装</title>
</head>

<body>
  <script>
    // 封装哈希表类
    // 链地址法来解决冲突
    function HashTable() {
      // 属性
      this.storage = [] // 元素容器
      this.count = 0    // 记录容器内元素个数
      this.limit = 7    // 表长度

      // 方法
      // 哈希函数
      HashTable.prototype.hashFun = function (str, size) {
        // 1.定义hashCode变量
        let hashCode = 0
        // 2.霍纳算法,计算hashCode的值
        for (let i = 0; i < str.length; i++) {
          hashCode = 10 * hashCode + str.charCodeAt(i)
        }
        // 3.取余操作
        let index = hashCode % size
        return index
      }

      // 插入修改操作
      HashTable.prototype.put = function (key, value) {
        // 1.根据key获取对应的index
        let index = this.hashFun(key, this.limit)
        // 2.根据index取出bucket(桶)
        let bucket = this.storage[index]
        // 3.判断bucket是否为null
        if (bucket == null) {
          bucket = []
          this.storage[index] = bucket
        }
        // 4.判断是否是修改数据
        for (let i = 0; i < bucket.length; i++) {
          let tuple = bucket[i]
          if (tuple[0] == key) {
            tuple[1] = value
            return
          }
        }
        // 5.进行添加操作
        bucket.push([key, value])
        this.count += 1

        // 6.判断是否需要扩容操作
        if (this.count > this.limit * 0.75) {
          let newSize = this.limit * 2
          //质数转换
          let newPrime = this.getPrime(newSize)
          this.resize(newPrime)
        }
      }

      // 获取操作
      HashTable.prototype.get = function (key) {
        // 1.根据key获取index
        let index = this.hashFun(key, this.limit)
        // 2.根据index获取bucket
        const bucket = this.storage[index]
        // 3.判断bucket是否为null
        if (bucket == null) {
          return null
        }
        // 4.有bucket,就进行线性查找
        for (let i = 0; i < bucket.length; i++) {
          const tuple = bucket[i]
          if (tuple[0] == key) {
            return tuple[1]
          }
        }
        // 5.依然没有找到,就返回null
        return null
      }

      // 删除操作
      HashTable.prototype.remove = function (key) {
        // 1.根据key获取index
        let index = this.hashFun(key, this.limit)
        // 2.根据index获取bucket
        const bucket = this.storage[index]
        // 3.判断bucket是否为null
        if (bucket == null) {
          return null
        }
        // 4.线性查找key对应的value,删除
        for (let i = 0; i < bucket.length; i++) {
          const tuple = bucket[i]
          if (tuple[0] == key) {
            bucket.splice(i, 1)
            this.count--
            return tuple[1]

            // 缩小哈希表容量
            if (this.limit > 7 && this.count < this.limit * 0.25) {
              let newSize = Math.floor(this.limit / 2)
              // 质数转换
              let newPrime = this.getPrime(newSize)
              this.resize(newPrime)
            }
          }
        }
        // 5.依然没有找到,就返回null
        return null
      }
      // 其他方法
      // 判断哈希表是否为空
      HashTable.prototype.isEmpty = function () {
        return this.count == 0
      }
      // 获取哈希表中元素的个数
      HashTable.prototype.size = function () {
        return this.count
      }
      // 哈希表扩大容量/缩小容量
      HashTable.prototype.resize = function (newLimit) {
        // 1.保存旧的数组内容
        const oldStorage = this.storage
        // 2.重置所有属性
        this.storage = []
        this.count = 0
        this.limit = newLimit
        // 3.遍历oldStorage中所有的bucket
        for (let i = 0; i < oldStorage.length; i++) {
          // 3.1取出对应的bucket
          const bucket = oldStorage[i]
          // 3.2判断bucket是否为null
          if (bucket == null) {
            continue
          }
          // 3.3bucket中有数据,取出数据,重新插入
          for (let i = 0; i < bucket.length; i++) {
            const tuple = bucket[i]
            this.put(tuple[0], tuple[1])
          }
        }
      }
      // 判断一个数是否是质数(素数)
      // 特点:只能被1和本身整除,不能被2到num-1之间的数整除
      function isPrime(num) {
        // 1.获取平方根
        let temp = parseInt(Math.sqrt(num))
        // 2.循环判断
        for (let i = 2; i <= temp; i++) {
          if (num % i == 0) return false
        }
        return true
      }
      // 获取质数方法
      HashTable.prototype.getPrime = function (num) {
        while(!this.isPrime(num)){
          num++
        }
      }
    }

    // let test = new HashTable()
    // test.put('ass', 'zhangsan')
    // test.put('ba2s', 'lisi1')
    // test.put('baes', 'lisi2')
    // test.put('bas', 'lisi3')
    // test.put('cdf', 'wangwu')
    // test.put('cdf1', 'wangwu')
    // test.put('cdf2', 'wangwu')
    // test.put('cdf3', 'wangwu')
    // console.log(test.storage);

  </script>
</body>

</html>